#pragma once

#include <unordered_set>
#include <queue>
#include "common.h"

// 基于邻接表的图广度优先遍历
std::vector<int> graphBFS(GraphAdjList& graph, const int start = 0) 
{
    std::vector<int> res_;                        // 返回的结果
    std::unordered_set<int> visited_{start};      // 无需集合，用于记录已经访问过的定顶点
    
    std::queue<int> queue_;
    queue_.push(start);
    while (!queue_.empty()) {
        int vertex_ = queue_.front();
        queue_.pop();

        res_.push_back(vertex_);

        for (auto neighbor_ : graph.getAdjList().at(vertex_)) {
            if (visited_.count(neighbor_))
                continue;
            queue_.push(neighbor_);
            visited_.emplace(neighbor_);
        }
    }
    return res_;
}

// std::vector<int> graphBFS(GraphAdjMat& graph, const int start = 0) {

// }


void dfs(GraphAdjList &graph, 
        std::unordered_set<int> &visited, 
        std::vector<int> &res, int vertex) 
{
    res.push_back(vertex);
    visited.emplace(vertex);
    for(int neighbor : graph.getAdjList().at(vertex)) {
        if (visited.count(neighbor) > 0)
            continue;
        dfs(graph, visited, res, neighbor);
    }
}

std::vector<int> graphDFS(GraphAdjList& graph, 
    const int start = 0) 
{
    std::vector<int> res_;                 // 返回的结果
    std::unordered_set<int> visited_;      // 无序集合，用于记录已经访问过的定顶点
    
    dfs(graph, visited_, res_, start);
    return res_;
}



// std::vector<int> graphDFS(GraphAdjMat& graph, const int start = 0) {

// }

void printVector(std::vector<int>& vector) {
    for (const auto& val : vector) {
        printf("%2d ", val);
    }
    printf("\n");
}

int main(int argc, char** argv) {
    AdjMatrix edges{{0,2},{0,4},{1,4},{1,2},{3,4},{1,3}};

    // GraphAdjMat graph(5, edges);

    // graph.printGraph();

    // std::vector<int> vec(0, 0);


    GraphAdjList graph(5, edges);

    // graph.printGraph();

    GraphAdjList graph2(5, graph.getAdjList());
    graph2.printGraph();

    // std::vector<int> res = graphBFS(graph2, 0);
    // printVector(res);

    std::vector<int> res = graphDFS(graph2, 0);
    printVector(res);

    return 0;
}